package edu.dayu.demo2;

/**
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组,并返回其长度。
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 * 思路：已知条件 数组的长度， 要求最小的子数组，也就是说可能存在很多个都满足条件。
 *      双重循环应该可解, 时间太久了。
 *      滑动窗口，这题最好的解决方案。从 0开始加 加到大于等于的时候就 减去0，如果还大于就继续，小于了就往前面加
 */
public class 和大于等于target的最短子数组 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        System.out.println(minSubArrayLen1(11,nums));
    }

    public static int minSubArrayLen(int target, int[] nums) {
        int min =0;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (sum >= target){
                min = 1;
                break;
            }
            for (int j = i+1; j < nums.length; j++) {
                sum+=nums[j];
                if (sum >= target){
                    if (min>(j-i+1)||min==0)
                        min = j-i+1;
                    break;
                }
            }
        }
        return min;
    }

    public static int minSubArrayLen1(int target, int[] nums){
        int start = 0;
        int end = 0;
        int sum = 0;
        int mix = nums.length+1;
        while (end<nums.length){
            sum+=nums[end];
            while (sum>=target){
                mix =Math.min(mix,end-start+1);
                sum-=nums[start++];
            }
            end++;
        }
        return mix==nums.length+1?0:mix;
    }
}
